package leetcode_动态规划;

import java.util.Arrays;

/**
 * 至多 K 次操作后的最长回文子序列
 * 算法: 动态规划（区间 DP）
 * LC_516 升级版
 *
 * @author yezh
 * @date 2025/3/3 17:02
 */
public class _3472 {

    public int longestPalindromicSubsequence(String s, int k) {
        char[] c = s.toCharArray();
        int n = c.length;
        int[][][] memo = new int[k + 1][n][n];
        for (int[][] mat : memo) for (int[] row : mat) Arrays.fill(row, -1);
        return dfs(0, n - 1, k, c, memo);
    }

    int dfs(int i, int j, int k, char[] c, int[][][] memo) {
        if (i >= j) return j - i + 1;
        if (memo[k][i][j] != -1) return memo[k][i][j];
        int res = c[i] == c[j] ?
                dfs(i + 1, j - 1, k, c, memo) + 2 :
                Math.max(dfs(i + 1, j, k, c, memo), dfs(i, j - 1, k, c, memo));
        int d = Math.abs(c[i] - c[j]);
        int op = Math.min(d, 26 - d);
        if (op <= k) res = Math.max(res, dfs(i + 1, j - 1, k - op, c, memo) + 2);
        memo[k][i][j] = res;
        return res;
    }

}
